/**
 * \file PageMap.cc
 * \brief Page bitmap allocator
 * \author Corey Tabaka
 */

/*
   Copyright 2006 Corey Tabaka

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/

#include <platform/PageMap.h>
#include <platform/PageTable.h>

#include <stdio.h>
#include <i386/mem.h>

typedef union {
	struct {
		uint32 reserved		: 12;
		uint32 bit			: 5;
		uint32 block		: 5;
		uint32 superBit		: 5;
		uint32 superBlock	: 5;
	};
	struct {
		uint32 reserved2	: 12;
		uint32 index		: 10;
		uint32 section		: 10;
	};
	struct {
		uint32 reserved3	: 12;
		uint32 page			: 20;
	};
	uint64 value;
} page_map_index_t;

/*
 * PageMap page allocation map
 */
PageMap::PageMap(void) {
	totalAlloc = 0;
	totalFree = 0;
	currentAlloc = 0;
}

PageMap::PageMap(uint32 base, uint32 limit) {
	initialize(base, limit);
}

PageMap::~PageMap(void) {
}

void PageMap::initialize(uint32 base, uint32 limit) {
	this->base = base & 0xfffff000;
	this->limit = limit & 0xfffff000;
	
	memset(super, 0xff, sizeof(super));
	memset(page, 0xff, sizeof(page));
	
	totalAlloc = 0;
	totalFree = 0;
	currentAlloc = 0;
	currentFree = (this->limit - this->base) >> 12;
}

bool PageMap::isFree(uint32 p) {
	bool ret;
	
	if (p >= base && p <= limit) {
		page_map_index_t addr;
		addr.value = p;
		
		if (page[addr.superBlock][addr.block] & (1 << addr.bit)) {
			ret = true;
		} else {
			ret = false;
		}
	} else {
		ret = false;
	}
	
	return ret;
}

inline void PageMap::updateMap(uint32 where) {
	page_map_index_t pm;
	pm.value = where;
	
	for (int i = 0; i < 32; i++) {
		if (page[pm.section][i] != 0) {
			super[pm.superBlock] |= (1 << pm.superBit);
			
			goto done;
		}
	}
	
	super[pm.superBlock] &= ~(1 << pm.superBit);

done:
	return;
}

static inline uint32 __ffs(uint32 val) {
	__asm__(
		"bsfl %1,%0"
		: "=r" (val)
		: "rm" (val));
	return val;
}

#define BIT_TEST(value, bit) ((value) & (1 << (bit)))

#define ADDR (*(volatile sint32 *) addr)

static inline int constant_test_bit(int nr, const volatile uint32 *addr) {
	return ((1UL << (nr & 31)) & (addr[nr >> 5])) != 0;
}

static inline int variable_test_bit(int nr, const volatile uint32 * addr) {
	int oldbit;

	__asm__ __volatile__(
		"btl %2,%1\n\tsbbl %0,%0"
		: "=r" (oldbit)
		: "m" (ADDR),"Ir" (nr));
	return oldbit;
}

#define test_bit(nr, addr)					\
	(__builtin_constant_p(nr) ?				\
		constant_test_bit((nr), (addr)) :	\
		variable_test_bit((nr), (addr))		\
	)

#undef ADDR

static inline int findFirstBit(const uint32 *addr, uint32 size) {
	int d0, d1;
	int res;

	/* This looks at memory. Mark it volatile to tell gcc not to move it around */
	__asm__ __volatile__(
		"xorl %%eax,%%eax\n\t"
		"repe; scasl\n\t"
		"jz 1f\n\t"
		"leal -4(%%edi),%%edi\n\t"
		"bsfl (%%edi),%%eax\n"
		"1:\tsubl %%ebx,%%edi\n\t"
		"shll $3,%%edi\n\t"
		"addl %%edi,%%eax"
		: "=a" (res), "=&c" (d0), "=&D" (d1)
		: "1" ((size + 31) >> 5), "2" (addr), "b" (addr) : "memory");
	return res;
}
		
bool PageMap::alloc(uint32 *there, uint32 len) {
	len = PAGE_ROUND(len);
	uint32 pages = len >> 12;
	
	bool ret = false;
	uint32 count = 0;
	
	// scan the sections for available chunks
	page_map_index_t pm;
	pm.value=base;
	
	while (pm.value <= limit) {
		if (BIT_TEST(super[pm.superBlock], pm.superBit)) {
			for (uint32 index = pm.index; index < 32*32
				&& pm.value <= limit; index++, pm.page++) {
				if (BIT_TEST(page[pm.section][pm.block], pm.bit)) {
					count++;
					
					if (count == pages) {
						reserve(pm.value - (len - PAGE_SIZE), len);
						*there = pm.value - (len - PAGE_SIZE);
						ret = true;
						
						//printf("Allocated %d pages at %08x\n", pages, *there);
						
						//totalAlloc += pages;
						//currentAlloc += pages;
						
						goto done;
					}
				} else {
					count = 0;
				}
			}		
		} else {
			count = 0;
			
			// skip the rest of this section
			// advance to the next section
			pm.section++;
			pm.index = 0;
		}
	}
			
			

done:			
	return ret;
}

bool PageMap::alloc(uint32 *there) {
	bool ret = false;
	
	// scan the sections for available pages
	page_map_index_t pm;
	pm.value=base;
	
	while (pm.value < limit) {
		if (BIT_TEST(super[pm.superBlock], pm.superBit)) {
			for (uint32 index = pm.index; index < 32*32
				&& pm.value < limit; index++, pm.page++) {
				if (BIT_TEST(page[pm.section][pm.block], pm.bit)) {
					// mark the page used
					page[pm.section][pm.block] &= ~(1 << pm.bit);
					updateMap(pm.value);
					
					*there = pm.value;
					ret = true;
					
					totalAlloc++;
					currentAlloc++;
					currentFree--;
					
					goto done;
				}
			}		
		} else {
			// advance to the next section
			pm.section++;
			pm.index = 0;
		}
	}
			
			

done:			
	return ret;
	
#if 0
	bool ret = false;
	
	// scan each super block segment
	for (int sseg = 0; sseg < 32; sseg++) {
		// find the set lsb of the super block segment dword
		int sbit;
		LSB_INDEX(super[sseg], sbit);
		
		// if there were any set bits in the segment
		// that is, any free pages in the corresponding page section
		if (sbit != -1) {
			// calc the page section index
			int sblock = sseg*32 + sbit;
			
			for (int bseg = 0; bseg < 32; bseg++) {
				// find the set lsb of the page segment dword
				int bit;
				LSB_INDEX(page[sblock][bseg], bit);
				
				
				if (bit != -1) {
					// clear the bit to mark page used
					page[sblock][bseg] &= ~(1 << bit);
					
					page_map_index_t pm;
					pm.superBlock = sseg;
					pm.superBit = sbit;
					pm.block = bseg;
					pm.bit = bit;
					pm.reserved = 0;
					
					// return the allocated address
					*there = pm.value;
					ret = true;
					
					goto done;
				}
			}
		}
	}

done:			
	return ret;
#endif
}

void PageMap::free(uint32 where, uint32 len) {
	where = where & 0xfffff000;
	len = PAGE_ROUND(len);
	
	if (where >= base && (where + len) <= limit) {
		uint32 end = where + len;
		
		//printf("Freeing %d pages at %08x\n", len/PAGE_SIZE, where);
			
		for (uint32 i=where; i < end; i += PAGE_SIZE) {
			page_map_index_t pm;
			pm.value = i;
			
			// mark the page free
			super[pm.superBlock] |= (1 << pm.superBit);
			page[pm.section][pm.block] |= (1 << pm.bit);
		}
		
		currentAlloc -= len >> 12;
		totalFree += len >> 12;
		currentFree += len >> 12;
	}
}

void PageMap::free(uint32 where) {
	where = where & 0xfffff000;
	
	if (where >= base && where <= limit) {
		page_map_index_t pm;
		pm.value = where;
		
		// mark the page free
		super[pm.superBlock] |= (1 << pm.superBit);
		page[pm.section][pm.block] |= (1 << pm.bit);
		
		currentAlloc--;
		totalFree++;
		currentFree++;
	}
}

void PageMap::reserve(uint32 where, uint32 len) {
	where = where & 0xfffff000;
	len = PAGE_ROUND(len);
	uint32 end = where + len;
	
	if (where >= base && end <= limit) {
		page_map_index_t pm;
		pm.value = where;
		
		while (pm.value < end) {
			uint32 value = pm.value; // save superblock info
			for (uint32 index = pm.index; index < 32*32 && pm.value < end;
				index++, pm.page++) {
				page[pm.section][pm.block] &= ~(1 << pm.bit);
				
				totalAlloc++;
				currentAlloc++;
				currentFree--;
			}
			
			updateMap(value); // update superblock
		}
		
		//totalAlloc += len >> 12;
		//currentAlloc += len >> 12;
	}
}

void PageMap::reserve(uint32 where) {
	if (where >= base && where <= limit) {
		page_map_index_t pm;
		pm.value = where;
		
		// mark the page used
		page[pm.section][pm.block] &= ~(1 << pm.bit);
		updateMap(where);
		
		totalAlloc++;
		currentAlloc++;
		currentFree--;
	}
}

uint32 PageMap::getAllocatedPages(void) {
	return currentAlloc;
}

uint32 PageMap::getPeakPages(void) {
	return totalAlloc;
}

uint32 PageMap::getFreedPages(void) {
	return totalFree;
}

uint32 PageMap::getFreePages(void) {
	return currentFree;
}

void PageMap::dump(void) {
	printf("Page map (%08x to %08x) total %d, current %d, free %d\n", base,
		limit, totalAlloc, currentAlloc, currentFree);
	printf("Superblock occupancy:\n");
	for (int i=32-1; i >= 0; i--) {
		printf("%08x", super[i]);
	}
	printf("\n");
}
